package org.review.algorithm.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

public class QuickSort {
    public static void main(String[] args) {
     /*   int[] arr = new int[]{-9, 78, 0, 23, 31, -567, -10, 70};
        Arrays.stream(arr).mapToObj(e -> e + " ").forEach(System.out::print);
        System.out.println("排序后");
         sort(arr, 0, arr.length - 1);
        //quickSort(arr, 0, arr.length - 1);
        Arrays.stream(arr).mapToObj(e -> e + " ").forEach(System.out::print);*/

        int size = 9000000;
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = (int) (Math.random() * size); // 生成一个[0, 8000000) 数
        }

        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
        String date1Str = simpleDateFormat.format(new Date());
        System.out.println("排序前的时间是=" + date1Str);
        sort(arr, 0, arr.length - 1);
        //quickSort(arr, 0, arr.length - 1);
        String date2Str = simpleDateFormat.format(new Date());
        System.out.println("排序后的时间是=" + date2Str);

    }

    public static void sort(int[] arr, int left, int right) {

        int l = left, r = right;
        int mid = arr[(right + left) / 2]; //TODO 2024/8/29:这里注意别携程r-l
        //TODO 2024/8/28:以中间数为准 进行调换位置
        while (l < r) {
            //TODO 2024/9/3:这里不能>=或<=，否则当中间mid两边全部小于或全部大于，会造成r=l，而且arr[r或l]不能与mid，此时死循环堆溢出
            while (mid > arr[l]) l++;  //TODO 2024/8/28:不满足小于中位数时 跳出循环
            while (mid < arr[r]) r--;

            if (r <= l) break;

            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            if (mid == arr[l]) {//TODO 2024/8/30: 这里处理当元素和mid相等的数时需要后移，否则有两个相同元素时就换一直互换
                l++;
            }
            if (mid == arr[r]) {
                r--;
            }
        }
        //TODO 2024/9/3:当l或r元素和mid相当就需要后退，否则 递归就有重复数
        if (mid == arr[l]) l--;
        if (mid == arr[r]) r++;

        if (left < l) {
            sort(arr, left, l);
        }
        if (r < right) {
            sort(arr, r, right);
        }
    }

    public static void sort2(int[] arr, int left, int right) {
        int l = left, r = right, temp;
        if (l >= r) return;
        temp = arr[l];
        while (l < r) {

            // TODO: 基数选择第一个元素《必须要先从r开始右移动》1.解释，https://blog.csdn.net/zcpvn/article/details/78150692
            //  如果选择最右元素，那么就要从l开始移动
            // TODO: 解释2.如果先从左边开始，当出现第一个大于基数的元素时，会将r指向的元素直接覆盖掉
            while (l < r && arr[r] >= temp) r--;
            arr[l] = arr[r];

            while (l < r && arr[l] <= temp) l++;
            arr[r] = arr[l];
        }
        arr[l] = temp;
        sort2(arr, left, l - 1);
        sort2(arr, l + 1, right);
    }

    public static void sort3(int[] arr, int left, int right) {
        if (left >= right) return;//TODO 2024/8/29:退出条件  要记得修改变量
        int l = left, r = right, mid = arr[(l + r) / 2];//TODO 2024/8/29: 因为mid 位置大概率是要修改的所以暂不考虑
        while (l < r) {
            //TODO 2024/8/29:此时跳出时机 应该是1两边都找到了 2：只有一边找到了，另外一边指向mid 3：都指向mid 此时跳出即可
            while (arr[l] < mid) {//TODO 2024/8/29:要么都小于mid 要么就是指向mid 没有第三种可能（不会跳过mid）
                l++;
            }
            while (mid < arr[r]) {//TODO 2024/8/29:要么都大于mid ，要么就是指向mid，也没有第三种可能
                r--;
            }

            //TODO 2024/8/29:考虑什么时候不需要替换，
            if (l >= r) break;
            //TODO 2024/8/29:交换位置，结合上边的分析 当一边指向mid 时候，就是和mid 交换
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //TODO 2024/8/30:处理数组中元素等于mid时 要掠过，否则就死循环卡在while这一步 l又不等于r，就一直交换
            if (mid == arr[l]) r--;
            if (mid == arr[r]) l++;
        }

        if (mid == arr[l]) l--;
        if (mid == arr[r]) r++;

        sort3(arr, left, l);
        sort3(arr, r, right);
    }


    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 找到分区点
            int pivotIndex = partition(arr, low, high);
            // 递归排序左半部分
            quickSort(arr, low, pivotIndex - 1);
            // 递归排序右半部分
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        // 选择最后一个元素作为基准
        int pivot = arr[high];
        int i = low - 1; // 小于基准元素的索引

        for (int j = low; j < high; j++) {
            // 如果当前元素小于基准
            if (arr[j] < pivot) {
                i++;
                // 交换 arr[i] 和 arr[j]
                swap(arr, i, j);
            }
        }
        // 交换 arr[i + 1] 和 arr[high]（基准元素）
        swap(arr, i + 1, high);
        return i + 1; // 返回基准元素的索引
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
